package Tree;

import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _230_KthSmallestElementinaBST {
    List<Integer> res = new ArrayList<>();
    //solution 1:recursion every level and sort the results
    public int kthSmallest_1(TreeNode root, int k) {
        addNode(root);
        int[] ans = new int[res.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = res.get(i);
        }
        Arrays.sort(ans);
        return ans[k - 1];
    }

    public void addNode(TreeNode root) {
        if (root != null) {
            res.add(root.val);
            addNode(root.left);
            addNode(root.right);
        }
    }

    //solution 2:as the tree is BST,so doesn't need to sort
    public int kthSmallest(TreeNode root, int k) {
        addBSTNode(root);
        return res.get(k - 1);
    }

    public void addBSTNode(TreeNode root) {
        if (root != null) {
            addBSTNode(root.left);
            res.add(root.val);
            addBSTNode(root.right);
        }
    }
}
